package arrAndstr;

import java.util.Stack;

/*
	19. 删除链表的倒数第 N 个结点
 */
public class T19 {
	public static class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	public static void main(String[] args) {
		ListNode head = new ListNode(1);

		removeNthFromEnd(head, 1);
	}

	public static ListNode removeNthFromEnd(ListNode head, int n) {
		// 提到倒数第n个，想到栈 -> 因为出站的第n个就是倒数第n个
		Stack<ListNode> stack = new Stack<>();
		ListNode node = head;
		while (node != null) {
			stack.push(node);
			node = node.next;
		}

		ListNode removeNode = new ListNode();
		while (n > 0) {
			removeNode = stack.pop();
			n--;
		}
		if (removeNode == head) {
			return head.next;
		}

		ListNode preNode = stack.pop();
		preNode.next = removeNode.next;

		return head;
	}
}
